#include <stdio.h>
#include "stdlib.h"
#include "stdlib.h"
#include "time.h"
typedef int ElementType;
typedef struct LNode *List;
struct LNode {
    ElementType data;
    List next;
};
List listInit() {
    List p;
    p = (List)malloc(sizeof (struct LNode));
    if(p == NULL) {
        printf("申请节点失败!");
    }
    p->next = NULL;
    return p;
}
void addLast(List Ptr,ElementType x) {
    List p,cur;
    cur = Ptr;
    p = (List)malloc(sizeof (struct LNode));
    p->data = x;
    p->next = NULL;
    while(cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = p;
    return;
}
int fib(int n) {
    int f1,f2,f3;
    f1 = 1;
    f2 = 1;
    if(n < 2) {
        return 1;
    }
    for (int i = 1; i < n; ++i) {
        f3 = f2 + f1;
        f1 = f2;
        f2 = f3;

    }
    return f3;
}
List findIndex(List Ptr,int index) {
    List cur = Ptr;
    for (int i = 0; i <= index; ++i) {
        cur = cur->next;
    }
    return cur;
}
void swap(List p,List s) {
    int tmp = p->data;
    p->data = s->data;
    s->data = tmp;
    return;
}
void knuth2(List Ptr,int n) {
    List p,s,cur,pre;
    srand((unsigned )time(NULL));
    for (int i = n  ; i >= 1 ; i--) {
        cur = Ptr;
        pre = Ptr;
        int x = rand()%(i + 1);
        p = findIndex(cur,n);
        s = findIndex(pre,x);
        swap(p,s);
    }
}
void merge(List L1,List L2) {
    List cur;
    cur = L1;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = L2;
    return;
}
void sort(List Ptr) {
    List min,cur;
    cur = Ptr;
    min = cur;
    while (cur) {
        while(cur) {
            if(min->data > cur->data) {
                int tmp = cur->data;
                cur->data = min->data;
                min->data = tmp;
            }
            cur = cur->next;
        }
        min = min->next;
        cur = min->next;
    }
    return;
}
int length(List Ptr) {
    List cur = Ptr;
    int count = 0;
    while (cur) {
        cur = cur->next;
        count++;
    }
    return count;
}
void delete(List Ptr,int index) {
    if(index < 1 || index > length(Ptr)) {
        printf("参数错误!");
    }
    List cur,pre;
    cur = Ptr;
    pre = cur;
    for (int i = 1; i < index; ++i) {
        pre = cur;
        cur = cur->next;
    }
    pre->next = cur->next;
    return;
}
void createL1(List Ptr) {
    for (int i = 1; i <= 10 ; i++) {
        int x = fib(i);
        addLast(Ptr, x);
    }
    return;
}
void createL2 (List Ptr) {
    int x = 4;
    addLast(Ptr,x);
    srand((unsigned )time(NULL));
    for (int i = 1; i < 10; ++i) {
        x = x + rand()%10;
        addLast(Ptr,x);
    }
    return;
}
int main() {
    List L1 = listInit();
    List L2 = listInit();
    List L3 = listInit();
    createL1(L1);
    List cur1 = L1->next;
    while (cur1) {

        printf("%d ",cur1->data);
        cur1 = cur1->next;
    }
    printf("\n");
    createL2(L2);
    List cur2 = L2->next;
    while (cur2) {
        printf("%d ",cur2->data);
        cur2 = cur2->next;
    }
    printf("\n");
    merge(L1,L2->next);
    knuth2(L1,19);
    List cur11 = L1->next;
    while (cur11) {
        printf("%d ",cur11->data);
        cur11 = cur11->next;
    }
    printf("\n");
    List cur111 = L1->next;
    sort(cur111);
    while (cur111) {
        printf("%d ",cur111->data);
        cur111 = cur111->next;
    }
    printf("\n");
    List cur3 = L1->next;
    delete(cur3,3);
    while (cur3) {
        printf("%d ",cur3->data);
        cur3 = cur3->next;
    }
    printf("\n");
    srand((unsigned )time(NULL));
    int c= rand()%100;
    addLast(L1,c);
    List cur4 = L1->next;
    while (cur4) {
        printf("%d ",cur4->data);
        cur4 = cur4->next;
    }
    printf("\n");
    sort(L1);
    List cur5 = L1->next;
    while (cur5) {
        printf("%d ",cur5->data);
        cur5 = cur5->next;
    }
//    int b = length(cur3);
//    printf("%d\n", b);
    return 0;
}
